// Set 在红黑树中体现为 key = value
// 不允许通过set迭代器改变set元素值
#pragma once

#include <functional>
#include <utility>
#include "../allocator/alloc.h"
#include "RB-Tree.h"

template <typename Key,
          typename Compare = std::less<Key>,
          typename Alloc = alloc>
class set
{

public:
    using key_type = Key;
    using value_type = Key;
    using key_compare = Compare;
    using value_compare = Compare;

private:
    template <typename T>
    struct identity
    {
        const T &operator()(const T &x) const noexcept
        {
            return x;
        }
        constexpr T &&operator()(T &&t) const noexcept
        {
            return std::forward<T>(t);
        }
    };
    using rep_type = rb_tree<
        key_type, value_type, identity<value_type>, key_compare, Alloc>;
    // Set 底层使用红黑树进行表示
    rep_type t;

public:
    using pointer = typename rep_type::const_pointer;
    using const_pointer = typename rep_type::const_pointer;
    using reference = typename rep_type::const_reference;
    using const_reference = typename rep_type::const_reference;
    // iterator被定义为RB_tree的const_iterator
    // 表示set的迭代器无法执行写入操作
    // 因为set的元素有一定的次序安排，不允许用户在（任意处）写入
    using iterator = typename rep_type::const_iterator;
    using const_iterator = typename rep_type::const_iterator;
    // Set 无法执行写入操作，一定都是const_iterator版本
    using reverse_iterator = typename rep_type::const_reverse_iterator;
    using const_reverse_iterator = typename rep_type::const_reverse_iterator;
    using size_type = typename rep_type::size_type;
    using difference_type = typename rep_type::difference_type;
    using self = set<Key, Compare, Alloc>;

public:

    // set 一定要使用rb_tree的insert_unique()而非是insert_equal
    // multiset才允许使用rb_tree的insert_equal()
    set() : t(Compare()) {};
    explicit set(const Compare& comp) : t(comp) {};

    template<typename InputIterator>
    set(InputIterator first, InputIterator last) : t(Compare())
    {
        t.insert_unique(first, last);
    }

    template<typename InputIterator>
    set(InputIterator first, InputIterator last, const Compare& comp) : t(comp)
    {
        t.insert_unique(first, last);
    }

    set(const self& other) : t(other.t) {}

    self& operator=(const self& other) 
    {
        t = other.t;
        return *this;
    }

    // 以下所有的set操作，RB-Tree都已经提供了，只需要传递调用即可
    key_compare key_comp() const { return t.key_comp(); }
    value_compare value_comp() const {return t.key_comp(); }
    iterator begin() const {return t.begin();}
    iterator end()   const {return t.end();}
    
    reverse_iterator rbegin() const {return t.rbegin();}

    reverse_iterator rend() const {return t.rend();}

    bool empty() const {return t.empty();}

    size_type size() const {return t.size();}

    size_type max_size() const {return t.max_size();}

    void swap(set<Key, Compare, Alloc>& other) {t.swap(other.t);} 

    // insert / erase
    using pair_iterator_bool = std::pair<iterator, bool>;

    std::pair<iterator, bool> insert(const value_type& x)
    {
        std::pair<typename rep_type::iterator, bool> p = t.insert_unique(x);
        return {p.first, p.second};
    }

    iterator insert(iterator position, const value_type& x)
    {
        using rep_iterator = typename rep_type::iterator;
        return t.insert_unique((rep_iterator&)position, x);
    }

    template<typename InputIterator>
    void insert(InputIterator first, InputIterator last)
    {
        t.insert_unique(first, last);
    }

    void erase(iterator position)
    {
        using rep_iterator = typename rep_type::iterator;
        t.erase((rep_iterator&) position);
    }

    size_type erase(const key_type& x)
    {
        return t.erase(x);
    }

    void erase(iterator first, iterator last)
    {
        using rep_iterator = typename rep_type::iterator;
        t.erase((rep_iterator&)first, (rep_iterator&)last);
    }

    void clear() {t.clear();}

    iterator find(const key_type& x) {return t.find(x);}

    size_type count(const key_type& x) {return t.count(x);}

    // for set iterator == const_iterator
    iterator lower_bound(const key_type& x) const {return t.lower_bound(x);}

    iterator upper_bound(const key_type& x) const {return t.upper_bound(x);}

    std::pair<iterator, iterator> equal_range(const key_type& x) {return t.equal_range(x);}

    template<typename _Key, typename _Compare, typename _Alloc>
    friend bool operator==(const set<_Key, _Compare, _Alloc>&, const set<_Key, _Compare, _Alloc>&);

    template<typename _Key, typename _Compare, typename _Alloc>
    friend bool operator<(const set<_Key, _Compare, _Alloc>&, const set<_Key, _Compare, _Alloc>&);

};

template<typename Key, typename Compare, typename Alloc>
inline bool operator==(const set<Key, Compare, Alloc>& x, const set<Key, Compare, Alloc>& y)
{
    return x.t == y.t;
}

template<typename Key, typename Compare, typename Alloc>
inline bool operator<(const set<Key, Compare, Alloc>& x, const set<Key, Compare, Alloc>& y)
{
    return x.t < y.t;
}